package algorithm.easy;

import java.util.*;

public class Solution94 {


    public static List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList();
        TreeNode temp = root;
        stack.push(temp);
        while(temp!=null && !stack.isEmpty()){
            temp = temp.left;
            if(temp!=null){
                stack.push(temp);
            }else{
                temp = stack.pop();
                list.add(temp.val);
                if(temp.right!=null){
                    temp = temp.right;
                    stack.push(temp);
                }
            }
        }


        return list;
    }

    public static void main(String[] args){
        TreeNode treeNode = TreeNode.init94();
        List<Integer> list = inorderTraversal(treeNode);
        System.out.println(list);
    }
}
